| 翻訳と辞書 |
| Bramble (graph theory) ： ウィキペディア英語版 |
Bramble (graph theory)
In graph theory, a bramble for an undirected graph ''G'' is a family of connected subgraphs of ''G'' that all touch each other: for every pair of disjoint subgraphs, there must exist an edge in ''G'' that has one endpoint in each subgraph. The ''order'' of a bramble is the smallest size of a hitting set, a set of vertices of ''G'' that has a nonempty intersection with each of the subgraphs. Brambles may be used to characterize the treewidth of ''G''.〔. In this reference, brambles are called "screens" and their order is called "thickness".〕
==Treewidth and havens==
A haven of order ''k'' in a graph ''G'' is a function ''β'' that maps each set ''X'' of fewer than ''k'' vertices to a connected component of ''G'' − ''X'', in such a way that every two subsets ''β''(''X'') and ''β''(''Y'') touch each other. Thus, the set of images of ''β'' forms a bramble in ''G'', with order ''k''. Conversely, every bramble may be used to determine a haven: for each set ''X'' of size smaller than the order of the bramble, there is a unique connected component ''β''(''X'') that contains all of the subgraphs in the bramble that are disjoint from ''X''.
As Seymour and Thomas showed, the order of a bramble (or equivalently, of a haven) characterizes treewidth: a graph has a bramble of order ''k'' if and only if it has treewidth at least .〔
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Bramble (graph theory)」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|